home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / exampleCode / viewkit / xcontact / parody / tnode.c++ < prev   
Encoding:
C/C++ Source or Header  |  1994-08-02  |  10.2 KB  |  369 lines
  1. // ------------- tnode.c++
  2.  
  3. // ===============================
  4. // B-tree Tnode class
  5. // ===============================
  6.  
  7. #include "parody.h"
  8.  
  9. TNode::TNode(Btree *bt, NodeNbr nd) :
  10.                             Node(&(bt->IndexFile()), nd)
  11. {
  12.     btree = bt;
  13.     currkey = NULL;
  14.     fstream& nf = btree->IndexFile().Nfile();
  15.     // ------- read the header
  16.     long nad = NodeAddress() + Node::NodeHeaderSize();
  17.     nf.seekg(nad);
  18.     nf.read((char *) &header, sizeof(TNodeHeader));
  19.     if (nf.eof() || nf.fail())    {
  20.         nf.clear();
  21.         // ----- appending a new node
  22.         nf.seekp(nad);
  23.         nf.write((char *) &header, sizeof(TNodeHeader));
  24.     }
  25.     else     {
  26.         // ---- reading an existing node, read the keys
  27.         for (int i = 0; i < header.keycount; i++)    {
  28.             // ---- get memory for and read a key
  29.             Key *thiskey = btree->NullKey()->Make();
  30.             thiskey->Key::operator=(*btree->NullKey());
  31.             thiskey->Read(nf);
  32.  
  33.             // ---- read the key's file address
  34.             NodeNbr fa;
  35.             nf.read((char *)&fa, sizeof(NodeNbr));
  36.             thiskey->fileaddr = fa;
  37.  
  38.             if (!header.isleaf)    {
  39.                 NodeNbr lnode;
  40.                 nf.read((char *)&lnode, sizeof(NodeNbr));
  41.                 thiskey->lowernode = lnode;
  42.             }
  43.             thiskey->AppendListEntry(&keys);
  44.         }
  45.     }
  46. }
  47.  
  48. // -------- write a key to the node's disk record
  49. void TNode::WriteKey(Key *thiskey)
  50. {
  51.     long kl;
  52.     fstream& nf = btree->IndexFile().Nfile();
  53.     if (btree->KeyLength() == 0)
  54.         kl = nf.tellp();
  55.     // -------- write the key value
  56.     thiskey->Write(nf);
  57.     // ---- write the key's file address
  58.     NodeNbr fa = thiskey->fileaddr;
  59.     nf.write((char *)&fa, sizeof(NodeNbr));
  60.     // ------- post the key length in the btree header
  61.     if (btree->KeyLength() == 0)    {
  62.         long km = nf.tellp();
  63.         btree->SetKeyLength((int) (km - kl));
  64.     }
  65.     if (!header.isleaf)    {
  66.         // --- write the lower node pointer for non-leaf keys
  67.         NodeNbr lnode = thiskey->lowernode;
  68.         nf.write((char *)&lnode, sizeof(NodeNbr));
  69.     }
  70. }
  71.  
  72. TNode::~TNode()
  73. {
  74.     if (header.keycount == 0)
  75.         // ---- this node is to be deleted
  76.         deletenode = pTrue;
  77.     else    {
  78.         fstream& nf = btree->IndexFile().Nfile();
  79.         if (nodechanged)    {
  80.             long nad = NodeAddress() + Node::NodeHeaderSize();
  81.             nf.seekp(nad);
  82.             // ------- write the node header
  83.             nf.write((char *) &header, sizeof(TNodeHeader));
  84.             nf.sync();
  85.         }
  86.         // ------- write the keys
  87.         Key *thiskey = (Key *) keys.FirstListEntry();
  88.         while (thiskey != NULL)    {
  89.             if (nodechanged)
  90.                 WriteKey(thiskey);
  91.             Key *nkey = (Key *) (thiskey->NextListEntry());
  92.             delete thiskey;
  93.             thiskey = nkey;
  94.         }
  95.         if (nodechanged)    {
  96.             // ------ pad the node
  97.             int em = m();
  98.             for (int i = header.keycount; i < em; i++)
  99.                 WriteKey(btree->NullKey());
  100.  
  101.             int nodesize =
  102.                 NodeHeaderSize() + em * btree->KeyLength();
  103.             if (!header.isleaf)
  104.                 nodesize += em * sizeof(NodeNbr);
  105.             int residual = nodelength - nodesize;
  106.             if (residual > 0)    {
  107.                 char *fill = new char[residual];
  108.                 memset(fill, 0, residual);
  109.                 nf.write(fill, residual);
  110.                 delete fill;
  111.             }
  112.         }
  113.     }
  114. }
  115.  
  116. // ------- assignment operator
  117. TNode& TNode::operator=(TNode &tnode)
  118. {
  119.     Key *thiskey;
  120.     // ---- if receiver has any keys, delete them
  121.     while (header.keycount > 0)    {
  122.         thiskey = (Key *) keys.FirstListEntry();
  123.         thiskey->DeleteListEntry();
  124.         delete thiskey;
  125.         --header.keycount;
  126.     }
  127.     Node::operator=(tnode);
  128.     header = tnode.header;
  129.     currkey = NULL;
  130.     // ------- copy the keys
  131.     thiskey = (Key *) tnode.keys.FirstListEntry();
  132.     while (thiskey != NULL)    {
  133.         Key *newkey = btree->NullKey()->Make();
  134.         *newkey = *thiskey;
  135.         newkey->AppendListEntry(&keys);
  136.         if (thiskey == tnode.currkey)
  137.             currkey = newkey;
  138.         thiskey = (Key *) (thiskey->NextListEntry());
  139.     }
  140.     return *this;
  141. }
  142.  
  143. // -------- compute m value of node
  144. int TNode::m()
  145. {
  146.     int keyspace = nodelength - NodeHeaderSize();
  147.     int keylen = btree->KeyLength();
  148.     if (!header.isleaf)
  149.         keylen += sizeof(NodeNbr);
  150.     return keyspace / keylen;
  151. }
  152.  
  153. // ---------- search a node for a match on a key
  154. pBool TNode::SearchNode(Key *keyvalue)
  155. {
  156.     currkey = (Key *) keys.FirstListEntry();
  157.     while (currkey != NULL)    {
  158.         if (*currkey > *keyvalue)
  159.             break;
  160.         if (*currkey == *keyvalue)    {
  161.             if (keyvalue->indexno == 0)
  162.                 return pTrue;
  163.             if (currkey->fileaddr == keyvalue->fileaddr)
  164.                 return pTrue;
  165.             if (keyvalue->fileaddr == 0)
  166.                 return pTrue;
  167.             if (currkey->fileaddr > keyvalue->fileaddr)
  168.                 break;
  169.         }
  170.         currkey = (Key *) (currkey->NextListEntry());
  171.     }
  172.     return pFalse;
  173. }
  174.  
  175. void TNode::Insert(Key *keyvalue)
  176. {
  177.     // -------- insert the new key
  178.     Key *ky = keyvalue->Make();
  179.     *ky = *keyvalue;
  180.     if (currkey == NULL)
  181.         ky->AppendListEntry(&keys);
  182.     else 
  183.         ky->InsertListEntry(currkey, &keys);
  184.     header.keycount++;
  185.     nodechanged = pTrue;
  186.     currkey = ky;
  187. }
  188.  
  189. // ---- a node "adopts" all its children by telling 
  190. //      them to point to it as their parent
  191. void TNode::Adoption()
  192. {
  193.     Adopt(header.lowernode);
  194.     Key *thiskey = (Key *) keys.FirstListEntry();
  195.     for (int i = 0; i < header.keycount; i++)    {
  196.         Adopt(thiskey->lowernode);
  197.         thiskey = (Key *) (thiskey->NextListEntry());
  198.     }
  199. }
  200.  
  201. // --- adopt a child node
  202. void TNode::Adopt(NodeNbr node)
  203. {
  204.     if (node)    {
  205.         TNode nd(btree, node);
  206.         nd.header.parent = nodenbr;
  207.         nd.nodechanged = pTrue;
  208.     }
  209. }
  210.  
  211. // ---- redistribute keys among two sibling nodes
  212. pBool TNode::Redistribute(NodeNbr sib)
  213. {
  214.     if (sib == 0)
  215.         return pFalse;
  216.     TNode sibling(btree, sib);
  217. //Commented out  by UMESH 
  218.       if (sibling.header.keycount >= sibling.m() ||
  219.               sibling.header.parent != header.parent)
  220.                   return pFalse;
  221. //Modification to the code commented out above by UMESH
  222. //    if(sibling.header.parent != header.parent)
  223. //        return pFalse;
  224.     // ---- assign left and right associations
  225.     TNode *left, *right;
  226.     if (sib == header.leftsibling)    {
  227.         right = this;
  228.         left = &sibling;
  229.     }
  230.     else    {
  231.         right = &sibling;
  232.         left = this;
  233.     }
  234.     // ------- compute number of keys to be in left node
  235.     int leftct =
  236.         (left->header.keycount + right->header.keycount) / 2;
  237.     // ------- if no redistribution would occur
  238.     if (leftct == left->header.keycount)
  239.         return pFalse;
  240.     // ------- compute number of keys to be in right node
  241.     int rightct =
  242.         (left->header.keycount+right->header.keycount)-leftct;
  243.     // ------- get the parent
  244.     TNode parent(btree, left->header.parent);
  245.     // --- position parent's currkey 
  246.     //     to one that points to siblings
  247.     parent.SearchNode((Key *)(left->keys.FirstListEntry()));
  248.     // ----- will move keys from left to right or right to
  249.     //         left depending on which node has the greater
  250.     //         number of keys to start with.
  251.     if (left->header.keycount < right->header.keycount)    {
  252.         // ----- moving keys from right to left
  253.         int mvkeys = right->header.keycount - rightct - 1;
  254.         // ----- move key from parent to end of left node
  255.         left->currkey = parent.currkey;
  256.         parent.currkey =
  257.             (Key *) parent.currkey->NextListEntry();
  258.         left->currkey->DeleteListEntry();
  259.         left->currkey->AppendListEntry(&left->keys);
  260.         if (!left->header.isleaf)
  261.             left->currkey->lowernode = right->header.lowernode;
  262.         // --- point to the keys to move 
  263.         //     (at front of right node)
  264.         Key *movekey = (Key *) right->keys.FirstListEntry();
  265.         // ---- move keys from right to left node
  266.         for (int i = 0; i < mvkeys; i++)    {
  267.             Key *nkey = (Key *) movekey->NextListEntry();
  268.             movekey->DeleteListEntry();
  269.             movekey->AppendListEntry(&left->keys);
  270.             movekey = nkey;
  271.         }
  272.         // --- move separating key from right node to parent
  273.         movekey->DeleteListEntry();
  274.         movekey->InsertListEntry(parent.currkey,&parent.keys);
  275.         if (!right->header.isleaf)
  276.             right->header.lowernode = movekey->lowernode;
  277.         movekey->lowernode = right->nodenbr;
  278.         right->header.keycount = rightct;
  279.         left->header.keycount  = leftct;
  280.         if (!left->header.isleaf)
  281.             left->Adoption();
  282.     }
  283.     else     {
  284.         // -------- moving from left to right
  285.         int mvkeys = left->header.keycount - leftct - 1;
  286.         // ----- move key from parent to right node
  287.         right->currkey = parent.currkey;
  288.         parent.currkey =
  289.             (Key *) parent.currkey->NextListEntry();
  290.         right->currkey->DeleteListEntry();
  291.         right->currkey->InsertListEntry(
  292.                     right->keys.FirstListEntry(), &right->keys);
  293.         if (!right->header.isleaf)
  294.             right->currkey->lowernode=right->header.lowernode;
  295.         // ----- locate the first key to move in the left node
  296.         Key *movekey = (Key *) (left->keys.FirstListEntry());
  297.         for (int i = 0; i < leftct; i++)
  298.             movekey = (Key *) movekey->NextListEntry();
  299.         // ----- move key from left node up to parent
  300.         Key *nkey = (Key *) movekey->NextListEntry();
  301.         movekey->DeleteListEntry();
  302.         movekey->InsertListEntry(parent.currkey,&parent.keys);
  303.         right->header.lowernode = movekey->lowernode;
  304.         movekey->lowernode = right->nodenbr;
  305.         movekey = nkey;
  306.         // --- move keys from the left node to the right node
  307.         Key *inskey = (Key *) right->keys.FirstListEntry();
  308.         for (i = 0; i < mvkeys; i++)    {
  309.             Key *nkey = (Key *) movekey->NextListEntry();
  310.             movekey->DeleteListEntry();
  311.             movekey->InsertListEntry(inskey, &right->keys);
  312.             movekey = nkey;
  313.         }
  314.         right->header.keycount = rightct;
  315.         left->header.keycount  = leftct;
  316.         if (!right->header.isleaf)
  317.             right->Adoption();
  318.     }
  319.     nodechanged =
  320.     sibling.nodechanged =
  321.     parent.nodechanged = pTrue;
  322.     return pTrue;
  323. }
  324.  
  325. // ------ implode the keys of two sibling nodes
  326. pBool TNode::Implode(TNode &right)
  327. {
  328.     int totkeys = right.header.keycount+header.keycount;
  329.     if (totkeys >= m() ||
  330.             right.header.parent != header.parent)
  331.         return pFalse;
  332.     nodechanged = right.nodechanged = pTrue;
  333.     header.rightsibling = right.header.rightsibling;
  334.     header.keycount += right.header.keycount+1;
  335.     right.header.keycount = 0;
  336.     // ---- get the parent of the imploding nodes
  337.     TNode parent(btree, header.parent);
  338.     parent.nodechanged = pTrue;
  339.     // ---- position parent's currkey to 
  340.     //      key that points to siblings
  341.     parent.SearchNode((Key *) keys.FirstListEntry());
  342.     // ---- move the parent's key to the left sibling
  343.     parent.currkey->DeleteListEntry();
  344.     parent.currkey->AppendListEntry(&keys);
  345.     parent.currkey->lowernode = right.header.lowernode;
  346.     parent.header.keycount--;
  347.     if (parent.header.keycount == 0)
  348.         // -- combined the last two leaf nodes into a new root
  349.         header.parent = 0;
  350.     // -- move the keys from the right sibling into the left
  351.     Key *movekey = (Key *) right.keys.FirstListEntry();
  352.     while (movekey != NULL)    {
  353.         Key *nkey = (Key *) movekey->NextListEntry();
  354.         movekey->DeleteListEntry();
  355.         movekey->AppendListEntry(&keys);
  356.         movekey = nkey;
  357.     }
  358.     if (header.rightsibling)    {
  359.         // - point right sibling of old right to imploded node
  360.         TNode farright(btree, header.rightsibling);
  361.         farright.header.leftsibling = GetNodeNbr();
  362.         farright.nodechanged = pTrue;
  363.     }
  364.     Adoption();
  365.     return pTrue;
  366. }
  367.  
  368.  
  369.